{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Jump to the End（跳到末尾）\n",
    "\n",
    "[@mjd507][1] ｜ [Wechat Channel（微信公众号）][2]\n",
    "\n",
    "![Logo][3]\n",
    "\n",
    "[1]: https://github.com/mjd507\n",
    "[2]: https://mp.weixin.qq.com/s/unRuXqbm-wdAn4ptyy0_FA\n",
    "[3]: https://mmbiz.qpic.cn/mmbiz_png/Yu0R50fg8IWZfGd8aswn52e6HlvPhQzqbGeDNkZFHtual83fmdO3j5rmz7YDcYicCUsOzspyDt6Ks1xibxATCaKQ/640?wx_fmt=png&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Starting at index $0$, for an element $n$ at index $i$, you are allowed to jump at most $n$ indexes ahead. Given a list of numbers, find the minimum number of jumps to reach the end of the list."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "从索引$0$开始，对于处在索引$i$的元素$n$，你可以向后跳跃最多$n$个索引。给定一个数组，确定到达数组末尾的最小跳跃次数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Starting point（初始模板）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def jumpToEnd(nums: list) -> int:\n",
    "    ''' Dynamic Programming Solution '''\n",
    "    \n",
    "    # Create a list and initialize them with infinity.\n",
    "    dinamic = [{'jumps': float('Inf'), 'path': '', 'index': ''}] * len(nums)\n",
    "    # Start from the first element, it jumps no times.\n",
    "    dinamic[0] = {'jumps': 0, 'path': str(nums[0]), 'index': '0'}\n",
    "    # Traverse all elements, then ...\n",
    "    for i in range(len(nums)):\n",
    "        # Get the value of current element.\n",
    "        n = nums[i]\n",
    "        # Traverse all position it can jump to, then ...\n",
    "        for j in range(1, n + 1):\n",
    "            # Check if it reaches the last element and ...\n",
    "            if i + j < len(nums):\n",
    "                # Select the fastest way to current position.\n",
    "                dinamic[i + j] = min(\n",
    "                    dinamic[i + j],\n",
    "                    {\n",
    "                        'jumps': dinamic[i]['jumps'] + 1,\n",
    "                        'path': dinamic[i]['path'] + ' -> ' + str(nums[j]),\n",
    "                        'index': dinamic[i]['index'] + ' -> ' +  str(i + j)\n",
    "                    },\n",
    "                    key=(lambda x: x['jumps'])\n",
    "                )\n",
    "            else:\n",
    "                # Otherwise, break and ckeck for the next jump.\n",
    "                break\n",
    "    # The jumping count of the last element is what we want.\n",
    "    return dinamic[-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Test cases（测试用例）\n",
    "\n",
    "```python\n",
    "Input: [3, 2, 5, 1, 1, 9, 3, 4]\n",
    "Output: 2\n",
    "```\n",
    "\n",
    "The minimum number of jumps to get to the end of the list is 2: \n",
    "```text\n",
    "3 -> 5 -> 4\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'jumps': 2, 'path': '3 -> 5 -> 9', 'index': '0 -> 2 -> 7'}"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "jumpToEnd([3, 2, 5, 1, 1, 9, 3, 4])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'jumps': 2, 'path': '4 -> 5 -> 3', 'index': '0 -> 4 -> 6'}"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "jumpToEnd([4, 1, 3, 1, 5, 2, 5])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'jumps': 2, 'path': '4 -> 5 -> 7', 'index': '0 -> 3 -> 7'}"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "jumpToEnd([4, 1, 2, 5, 7, 9, 7, 7])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'jumps': 1, 'path': '7 -> 8', 'index': '0 -> 6'}"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "jumpToEnd([7, 7, 5, 8, 2, 5, 8])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'jumps': 2, 'path': '4 -> 7 -> 7', 'index': '0 -> 1 -> 7'}"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "jumpToEnd([4, 7, 5, 1, 9, 4, 7, 3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'jumps': 4,\n",
       " 'path': '3 -> 9 -> 2 -> 1 -> 1',\n",
       " 'index': '0 -> 2 -> 5 -> 105 -> 106'}"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "jumpToEnd([3, 1, 9, 2, 1, 100, 1] + 49 * [1] + [2] + 50 * [1])"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
